package com.huangyi;

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        //连续数组
        class Solution {
            public int findMaxLength(int[] nums) {
                Map<Integer, Integer> hash = new HashMap<>();
                hash.put(0, -1); // 前缀和为0，默认出现在-1位置
                int sum = 0, ret = 0;

                for (int i = 0; i < nums.length; i++) {
                    // 0 记作 -1，1 记作 +1
                    sum += (nums[i] == 0 ? -1 : 1);

                    if (hash.containsKey(sum)) {
                        // 更新最长子数组长度
                        ret = Math.max(ret, i - hash.get(sum));
                    } else {
                        // 只记录第一次出现的位置
                        hash.put(sum, i);
                    }
                }
                return ret;
            }
        }
        //矩阵区域和
        class Solution2 {
            public int[][] matrixBlockSum(int[][] mat, int k) {
                int m = mat.length, n = mat[0].length;
                // 1. 预处理二维前缀和矩阵
                int[][] dp = new int[m+1][n+1];
                for(int i = 1; i <= m; i++){
                    for(int j = 1; j <= n; j++){
                        dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1];
                    }
                }

                // 2. 计算每个元素的 block sum
                int[][] answer = new int[m][n];
                for(int i = 0; i < m; i++){
                    for(int j = 0; j < n; j++){
                        int x1 = Math.max(0, i-k);
                        int y1 = Math.max(0, j-k);
                        int x2 = Math.min(m-1, i+k);
                        int y2 = Math.min(n-1, j+k);
                        answer[i][j] = dp[x2+1][y2+1] - dp[x1][y2+1] - dp[x2+1][y1] + dp[x1][y1];
                    }
                }
                return answer;
            }
        }
    }
}